Field of the Invention
The invention relates to a method for deinterleaving a data signal interleaved in blocks.
In telecommunications engineering, it is customary to interleave a data signal, which will be transmitted via a channel, at the transmitter end. As a result of the interleaving, interference that without interleaving would effect detection errors that are statistically dependent (occurring in groups) instead produces statistically independent detection errors. For statistically independent detection errors, by using channel coding a better degree of error protection can be achieved than for statistically dependent detection errors.
The interleaving and deinterleaving of the data signal is performed in data blocks. That is to say a respectively identical interleaving specification is used by the interleaver at the transmitter end to interleave data block by data block, and in the deinterleaver at the receiver, which deinterleaves using the inverse deinterleaving specification (likewise identical in each case).
For this purpose, it is necessary for the appropriate target addresses (interleaving target addresses or deinterleaving target addresses) to be calculated for resorting the data symbols before the first interleaving or deinterleaving. To date, this has been done in such a way that before carrying out the first interleaving or deinterleaving procedure, target addresses are calculated for all of the data symbols of a data block, and are stored in an interleaving target address memory or deinterleaving target address memory. In the case of a data block consisting of K data symbols, the target address memories must in each case include K target address memory locations. The target address memories therefore contain the complete interleaving and deinterleaving information.
It is disadvantageous in this method of deinterleaving that a large memory location area must be set up in the receiver. For the UMTS (Universal Mobile Telecommunications System) Standard, which permits a data block length K of between 40 and 5114 bits, a memory with 5114 memory locations with an address data width of 13 bits is required to store the deinterleaving target addresses.
Usually, the deinterleaving of a data signal is performed after the channel coding. In the case of a special form of channel coding, which is denoted as turbo coding, an interleaving procedure is carried out as early as during the channel coding. This interleaving carried out in the course of turbo coding is denoted below as turbo interleaving.
Turbo codes are binary, parallel-concatenated, recursive, systematic convolutional codes. Particularly in the case of the transmission of large data blocks consisting of more than, for example, 1000 bits, the use of turbo codes can achieve a substantially better degree of error protection than is possible with conventional convolutional codes. The structure of a turbo code and the generation of the turbo code by using a turbo coder with an integrated turbo interleaver are known and are described in detail, for example, in the book entitled “Analyse und Entwurf digitaler Mobilfunksysteme” [“Analysis and design of digital mobile radio systems”], by P, Jung, Stuttgart, B. G. Teubner-Verlag, 1997, Appendix E, pages 343–368.
Upon the reception of the turbo-coded data signal transmitted via a transmission channel (for example mobile radio channel), it is necessary for the turbo interleaving also to be cancelled in the receiver in the course of turbo decoding. This process is denoted as turbo deinterleaving and is accomplished by using a turbo deinterleaver integrated in the turbo decoder.
The turbo interleaving and deinterleaving of the data signal is likewise performed in data blocks.
International Publication WO 99/07076 describes an interleaving method in the case of which the interleaving addresses are calculated directly by using a controller as a function of various algorithmic specifications. The inverse deinterleaving process is intended to be implemented in the reverse sequence.
U.S. Pat. No. 5,677,911 specifies a method for segmental deinterleaving of a previously interleaved data stream. The segmental deinterleaving is achieved by virtue of the fact that the time delays of data words undertaken in the interleaving are cancelled in the deinterleaving operation.
U.S. Pat. No. 6,108,388 describes an interleaving method in the case of which, as in the UMTS Standard, both an inter-row permutation and an intra-row permutation are undertaken.